package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.LeetCode;
import com.zk.algorithm.annotation.Microsoft;
import com.zk.algorithm.bean.TreeNode;

import java.util.Stack;

/**
 * 二叉树 => 双向链表
 *
 * @author zk
 */
@Microsoft
@LeetCode("114")
public class FlattenBinaryTreeToLinkedList {

    public void flatten(TreeNode root) {
        if (root == null)
            return;

        Stack<TreeNode> stk = new Stack<TreeNode>();
        stk.push(root);

        while (!stk.isEmpty()) {
            TreeNode curr = stk.pop();
            if (curr.right != null)
                stk.push(curr.right);
            if (curr.left != null)
                stk.push(curr.left);
            if (!stk.isEmpty())
                curr.right = stk.peek();
            curr.left = null;  // dont forget this!!
        }
    }

}
